package com.jyl.data.impl;

import com.jyl.data.Map;

import java.util.function.BiConsumer;

/**
 * @ClassName HashTable
 * @Author admin
 * @Date 2024/6/13
 */
public class HashTable<K, V> implements Map<K, V> {

    private int size;

    private Entry<K, V>[] array = new Entry[16];

    private final static Double Load_Factor = 0.75;

    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

        public Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("[");
            Entry<K, V> current = this;
            do {
                builder.append("(").append(current.key).append(",").append(current.value).append(")").append("->");
                current = current.next;
            } while (current != null);
            builder.append("null]");
            return builder.toString();
        }
    }

    /**
     * 根据 key 和 len 计算 hash值
     *
     * @param key
     * @param len
     * @return
     */
    private int hash(K key, int len) {
        return key.hashCode() & Integer.MAX_VALUE % len;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void put(K key, V value) {
        int hash = hash(key, array.length);
        Entry<K, V> entry = null;
        if (array[hash] == null) { // 该索引位置上没有元素,把当前节点作为头节点
            entry = new Entry<>(key, value, null);
        } else {
            Entry<K, V> current = array[hash];
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            entry = new Entry<>(key, value, array[hash]);
        }
        array[hash] = entry;
        size++;

        //  (size / len > Load_Factor) 需要扩容
        if ((double) size / array.length > Load_Factor) {
            grow();
        }
    }

    /**
     * 步骤：
     * 1、遍历原数组 遍历原数组中的链表
     * 2、取原数组上某个索引位置的头节点 --> 拿到它的key和新数组的长度算出新的hash值
     */
    private void grow() {
        Entry<K, V>[] newArray = new Entry[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Entry<K, V> node = array[i];
            while (node != null) {

                Entry<K, V> next = node.next; // 由于下面的操作会将 node.next指向新数组的头节点，所以先记录一下

                int newIndex = hash(node.key, newArray.length); // 得到node在新数组中的索引位置

                // 但是，在新数组中该索引位置可能已经有链表存在了，我们应该获取到新数组中该索引位置的头节点
//                Entry<K, V> head = newArray[newIndex];
                /*
                  目的：将node放入新数组中的新索引位置
                    1. 若head为null，直接将新数组的索引指向 node即可
                    2. 若head不为null，则先将node指向head，然后再将数组的索引指向node
                 */
//                node.next = head;
//                newArray[newIndex] = node;

                // 简化书写
                node.next = newArray[newIndex];
                newArray[newIndex] = node;

                node = next; // 继续往下遍历
            }
        }
        array = newArray;
    }

    @Override
    public V get(K key) {
        int index = hash(key, array.length);
        Entry<K, V> node = array[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    @Override
    public V remove(K key) {
        int index = hash(key, array.length);
        Entry<K, V> node = array[index];

        V result = null;

        if (node != null) {
            if (node.key.equals(key)) {
                result = node.value;
                array[index] = node.next;
                size--;
            } else {
                Entry<K, V> pre = node;
                while (pre.next != null) {
                    if (pre.next.key.equals(key)) {
                        result = pre.next.value;
                        pre.next = pre.next.next;
                        size--;
                    }
                    pre = pre.next;
                }
            }
        }

        return result;
    }

    @Override
    public void forEach(BiConsumer<K, V> consumer) {
        for (int i = 0; i < array.length; i++) {
            Entry<K, V> node = array[i];
            while (node != null) {
                consumer.accept(node.key, node.value);
                node = node.next;
            }
        }
    }

}
